using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using HTCollections.Custom;
using Unity.Collections;
using Unity.Collections.LowLevel.Unsafe;

namespace HTCollections.Unsafe
{
    [StructLayout(LayoutKind.Sequential)]
    [DebuggerDisplay("Length = {Length}, Capacity = {Capacity}, IsCreated = {IsCreated}")]
    [DebuggerTypeProxy(typeof(UnsafeIntPriorityQueueDebugView))]
    [BurstCompatible(GenericTypeArguments = new[] { typeof(int) })]
    public unsafe struct UnsafeIntPriorityQueue
    {
        [NativeDisableUnsafePtrRestriction] public int* Ptr;
        public int Capacity;
        public int Length;
        public bool IsCreated;
        public Allocator Allocator;

        /// <summary>
        /// 是否为降序排列（大顶堆）
        /// </summary>
        public bool IsDescending;

        /// <summary>
        /// 创建优先级队列
        /// </summary>
        /// <param name="capacity">初始容量</param>
        /// <param name="isDescending">是否为降序排列（大顶堆）</param>
        /// <param name="allocator">分配器</param>
        /// <returns></returns>
        public static UnsafeIntPriorityQueue Create(int capacity = 4, bool isDescending = false,
            Allocator allocator = Allocator.Persistent)
        {
            UnsafeIntPriorityQueue list = new UnsafeIntPriorityQueue(capacity, isDescending, allocator);
            return list;
        }

        /// <summary>
        /// 优先级队列
        /// </summary>
        /// <param name="capacity">初始容量</param>
        /// <param name="isDescending">是否为降序排列（大顶堆）</param>
        /// <param name="allocator">分配器</param>
        public UnsafeIntPriorityQueue(int capacity = 4, bool isDescending = false,
            Allocator allocator = Allocator.Persistent)
        {
            IsDescending = isDescending;
            Allocator = allocator;
            Ptr = UnsafeUtil.Malloc<int>(capacity, allocator);
            Capacity = capacity;
            Length = 0;
            IsCreated = true;
        }

        public void Dispose()
        {
            if (!IsCreated) return;
            UnsafeUtil.Free(Ptr, Allocator);
            Ptr = null;
            Capacity = 0;
            Length = 0;
            Allocator = Allocator.Invalid;
            IsCreated = false;
        }

        public int this[int index]
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get
            {
                if (!IsCreated)
                    throw new Exception("UnsafeIntPriorityQueue is not created");

                CollectionsUtil.CheckIndexInRange(index, Length);

                return Ptr[index];
            }
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            set
            {
                if (!IsCreated)
                    throw new Exception("UnsafeIntPriorityQueue is not created");

                CollectionsUtil.CheckIndexInRange(index, Length);

                Ptr[index] = value;
            }
        }

        public void Enqueue(int value)
        {
            Add(value);
            if (IsDescending)
                Enqueue_Descending(); //大顶堆
            else
                Enqueue_Ascending(); //小顶堆
        }

        public int Dequeue()
        {
            if (Length == 1)
            {
                int ret = Ptr[0];
                Clear();
                return ret;
            }
            else
            {
                int lastIndex = Length - 1;
                Swap(0, lastIndex); //交换首尾元素
                int ret = Ptr[lastIndex];
                RemoveAt(lastIndex); //移除尾
                if (IsDescending)
                    UpdateHeap_Descending(0, lastIndex); //调整堆(大顶堆)
                else
                    UpdateHeap_Ascending(0, lastIndex); //调整堆(小顶堆)
                return ret;
            }
        }

        public int Peek()
        {
            return Ptr[0];
        }

        public void Clear()
        {
            if (!IsCreated)
                throw new Exception("UnsafeIntPriorityQueue is not created");
            if (Length == 0) return;
            UnsafeUtil.Clear(Ptr, Capacity);
            Length = 0;
        }


        /// <summary>
        /// 大顶堆
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void Enqueue_Descending()
        {
            int index = Length - 1;
            while (index > 0)
            {
                int index2 = (index - 1) / 2;
                var a = Ptr[index];
                var b = Ptr[index2];
                if (a < b) break; //子节点 >= 父节点
                Ptr[index] = b; //交换父子节点
                Ptr[index2] = a;
                index = index2; //更新 index
            }
        }

        /// <summary>
        /// 小顶堆
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void Enqueue_Ascending()
        {
            int index = Length - 1;
            while (index > 0)
            {
                int index2 = (index - 1) / 2;
                var a = Ptr[index];
                var b = Ptr[index2];
                if (a >= b) break; //子节点 < 父节点
                Ptr[index] = b; //交换父子节点
                Ptr[index2] = a;
                index = index2; //更新 index
            }
        }

        /// <summary>
        /// 调整（大顶）堆，Priority 值最大的在堆顶
        /// </summary>
        /// <param name="i">待调整的数据的索引</param>
        /// <param name="len">数据列表长度</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void UpdateHeap_Descending(int i, int len)
        {
            var temp = Ptr[i]; //记录待 调整 的值
            for (int k = 2 * i + 1; k < len; k = 2 * k + 1)
            {
                if (k + 1 < len) //存在右节点
                {
                    if (Ptr[k + 1] >= Ptr[k]) //右节点 >= 左节点
                    {
                        k += 1; //选择较大的右节点
                    }
                }

                //（左/右）子节点 >= 父节点
                if (Ptr[k] >= temp)
                {
                    Swap(k, i); //交换（要保证父节点一定大于子节点——大顶堆）
                    i = k; //更新 i ，继续下一次循环
                }
                //子节点<父节点
                else
                {
                    break; //跳出循环，此处不需要往深层次遍历的原因在于：在堆排序中是从最后一个非叶子节点开始倒着向前 UpdateHeap
                }
            }
        }

        /// <summary>
        /// 调整（小顶）堆，Priority 值最小的在堆顶
        /// </summary>
        /// <param name="i">待调整的数据的索引</param>
        /// <param name="len">数据列表长度</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void UpdateHeap_Ascending(int i, int len)
        {
            var temp = Ptr[i]; //记录待 调整 的值
            for (int k = 2 * i + 1; k < len; k = 2 * k + 1)
            {
                if (k + 1 < len) //存在右节点
                {
                    if (Ptr[k + 1] < Ptr[k]) //右节点 < 左节点
                    {
                        k += 1; //选择较小的右节点
                    }
                }

                //（左/右）子节点 < 父节点
                if (Ptr[k] < temp)
                {
                    Swap(k, i); //交换（要保证父节点一定小于子节点——小顶堆）
                    i = k; //更新 i ，继续下一次循环
                }
                //子节点>父节点
                else
                {
                    break; //跳出循环，此处不需要往深层次遍历的原因在于：在堆排序中是从最后一个非叶子节点开始倒着向前 UpdateHeap
                }
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void Swap(int a, int b)
        {
            var temp = Ptr[a];
            Ptr[a] = Ptr[b];
            Ptr[b] = temp;
        }

        /// <summary>
        /// 添加元素
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void Add(int value)
        {
            if (!IsCreated)
                throw new Exception("UnsafeIntPriorityQueue is not created");

            if (Length == Capacity)
            {
                int newCapacity = ArrayUtil.GetCapacity(Capacity);
                if (newCapacity == Capacity) return;
                Ptr = UnsafeUtil.ResizeUnsafeArray(Ptr, Capacity, newCapacity, Allocator);
                Capacity = newCapacity;
            }

            Ptr[Length] = value;
            Length++;
        }

        /// <summary>
        /// 删除指定索引元素
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        bool RemoveAt(int index)
        {
            if (index < 0 || index >= Length) return false;
            Length--;
            UnsafeUtil.MemCpy(Ptr, index + 1, Ptr, index, Length - index);
            Ptr[Length] = default;
            return true;
        }
    }

    sealed class UnsafeIntPriorityQueueDebugView
    {
        UnsafeIntPriorityQueue mArray;

        public UnsafeIntPriorityQueueDebugView(UnsafeIntPriorityQueue array)
        {
            mArray = array;
        }

        public int[] Items
        {
            get
            {
                int[] dst = new int[mArray.Length];
                unsafe
                {
                    UnsafeUtil.CopyArray(mArray.Ptr, 0, dst, 0, mArray.Length);
                }

                return dst;
            }
        }
    }
}